#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const long long N=3;
const long long MOD=200907;
struct Mat{
    long long m[N][N];
};
Mat operator * (Mat a,Mat b){
    Mat t;
    memset(t.m,0,sizeof(t.m));
    for(long long k=0;k<N;k++){
        for(long long i=0;i<N;i++){
            if(a.m[i][k]==0){
                continue;
            }
            for(long long j=0;j<N;j++){
                if(b.m[k][j]==0){
                    continue;
                }
                t.m[i][j]=(t.m[i][j]+(a.m[i][k]*b.m[k][j]))%MOD;
            }
        }
    }
    return t;
}
Mat operator ^ (Mat a,long long n){
    // for(long long i=0;i<N;i++){
    //     for(long long j=0;j<N;j++){
    //         prlong longf("%d ",a.m[i][j]);
    //     }
    //     prlong longf("\n");
    // }
    Mat t;
    for(long long i=0;i<N;i++){
        for(long long j=0;j<N;j++){
            t.m[i][j]=i==j?1:0;
        }
    }
    while(n){
        if(n%2){
            t=t*a;
        }
        n/=2;
        a=a*a;
    }
    // for(long long i=0;i<N;i++){
    //     for(long long j=0;j<N;j++){
    //         prlong longf("%d ",t.m[i][j]);
    //     }
    //     prlong longf("\n");
    // }
    return t;
}
int main(void){
    long long n;
    Mat a;
    a.m[0][0]=a.m[0][1]=a.m[2][0]=a.m[2][2]=1;
    a.m[0][2]=a.m[1][1]=a.m[1][2]=a.m[2][1]=0;
    a.m[1][0]=2;
    Mat b;
    memset(b.m,0,sizeof(b.m));
    b.m[0][0]=2;
    b.m[0][1]=1;
    b.m[0][2]=1;
    while(~scanf("%d",&n) && n){
        if(n==1){
            printf("1\n");
        }
        else if(n==2){
            printf("2\n");
        }
        else{
            long long ans=(b*(a^(n-2))).m[0][0]%MOD;
            printf("%d\n",ans);
        }
    }
    return 0;
}